package com.yanceysong.codetop.s21_s30;

/**
 * @ClassName S27_Easy_415_字符串相加
 * @Description
 * @date 2025/09/16
 * @Author yanceysong
 * @Version 1.0
 */
public class S27_Easy_415_字符串相加 {

    /**
     * S27_Easy_415_字符串相加
     * <p>
     * LeetCode：
     * <a href="https://leetcode.cn/problems/add-strings/description/">...</a>
     * <p>
     * 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
     * <p>
     * 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
     * <p>
     * 示例 1：
     * <p>
     * 输入：num1 = "11", num2 = "123"
     * 输出："134"
     * <p>
     * 示例 2：
     * <p>
     * 输入：num1 = "456", num2 = "77"
     * 输出："533"
     * <p>
     * 示例 3：
     * <p>
     * 输入：num1 = "0", num2 = "0"
     * 输出："0"
     * <p>
     * 提示：
     * <p>
     * 1 <= num1.length, num2.length <= 10^4
     * num1 和num2 都只包含数字字符
     * num1 和num2 都不包含任何前导零
     * <p>
     * 使用模拟竖式加法的方式实现字符串相加
     * <p>
     * 算法原理：
     * 1. 从两个字符串的末尾开始，逐位相加
     * 2. 维护一个进位变量carry，处理相加结果大于等于10的情况
     * 3. 将每一位的计算结果添加到结果字符串中
     * 4. 最后反转结果字符串得到最终答案
     * <p>
     * 核心思想：
     * - 模拟手工计算加法的过程
     * - 从最低位(个位)开始计算，逐步向高位进行
     * - 处理不同长度字符串的对齐问题
     * - 正确处理进位
     * <p>
     * 图解示例：num1 = "456", num2 = "77"
     * <p>
     * 竖式加法过程：
     * 4 5 6
     * +     7 7
     * ---------
     * 5 3 3
     * <p>
     * 详细计算过程：
     * <p>
     * 初始状态：
     * num1 = "456" (索引: 0,1,2)
     * num2 = "77"  (索引: 0,1)
     * firstPointer = 2 (指向'6')
     * secondPointer = 1 (指向'7')
     * carryValue = 0
     * result = ""
     * <p>
     * 第1步：计算个位 (6 + 7)
     * firstDigit = 6 (num1[2])
     * secondDigit = 7 (num2[1])
     * digitSum = 6 + 7 + 0 = 13
     * result.append(13 % 10) → result = "3"
     * carryValue = 13 / 10 = 1
     * firstPointer = 1, secondPointer = 0
     * <p>
     * 第2步：计算十位 (5 + 7 + 进位1)
     * firstDigit = 5 (num1[1])
     * secondDigit = 7 (num2[0])
     * digitSum = 5 + 7 + 1 = 13
     * result.append(13 % 10) → result = "33"
     * carryValue = 13 / 10 = 1
     * firstPointer = 0, secondPointer = -1
     * <p>
     * 第3步：计算百位 (4 + 0 + 进位1)
     * firstDigit = 4 (num1[0])
     * secondDigit = 0 (num2已结束，取0)
     * digitSum = 4 + 0 + 1 = 5
     * result.append(5 % 10) → result = "335"
     * carryValue = 5 / 10 = 0
     * firstPointer = -1, secondPointer = -1
     * <p>
     * 最终步骤：反转结果
     * result.reverse() → "533"
     * <p>
     * 时间复杂度：O(max(m,n))，其中m和n分别是两个字符串的长度
     * 空间复杂度：O(max(m,n))，用于存储结果字符串
     */
    public String addStrings(String num1, String num2) {
        // 边界条件检查
        if (num1 == null || num1.isEmpty()) return num2 == null ? "0" : num2;
        if (num2 == null || num2.isEmpty()) return num1;

        StringBuilder resultBuilder = new StringBuilder();
        int carryValue = 0; // 进位值

        // 双指针：分别指向两个字符串的末尾（最低位）
        int firstPointer = num1.length() - 1;   // 指向第一个数字字符串的当前位
        int secondPointer = num2.length() - 1;  // 指向第二个数字字符串的当前位

        // 当还有数位需要处理或者还有进位时继续循环
        while (firstPointer >= 0 || secondPointer >= 0 || carryValue != 0) {
            // 获取当前位的数字，如果已经超出字符串范围则取0
            int firstDigit = firstPointer >= 0 ? num1.charAt(firstPointer) - '0' : 0;
            int secondDigit = secondPointer >= 0 ? num2.charAt(secondPointer) - '0' : 0;

            // 计算当前位的和（包括进位）
            int digitSum = firstDigit + secondDigit + carryValue;

            // 将当前位的结果添加到结果字符串（注意：是逆序添加）
            resultBuilder.append(digitSum % 10);

            // 更新进位值
            carryValue = digitSum / 10;

            // 移动指针到下一位（更高位）
            firstPointer--;
            secondPointer--;
        }

        // 反转结果字符串得到正确的顺序
        return resultBuilder.reverse().toString();
    }

    public static void main(String[] args) {
        S27_Easy_415_字符串相加 solution = new S27_Easy_415_字符串相加();

        System.out.println("=== 字符串相加算法测试开始 ===");

        // 测试1: 题目示例1 - "11" + "123"
        System.out.println("\n--- 测试1: 基础示例 \"11\" + \"123\" ---");
        testCase1(solution);

        // 测试2: 题目示例2 - "456" + "77"
        System.out.println("\n--- 测试2: 不同长度 \"456\" + \"77\" ---");
        testCase2(solution);

        // 测试3: 题目示例3 - "0" + "0"
        System.out.println("\n--- 测试3: 零相加 \"0\" + \"0\" ---");
        testCase3(solution);

        // 测试4: 边界情况 - 单位数相加
        System.out.println("\n--- 测试4: 单位数相加 \"1\" + \"9\" ---");
        testSingleDigits(solution);

        // 测试5: 进位测试 - "999" + "1"
        System.out.println("\n--- 测试5: 多重进位 \"999\" + \"1\" ---");
        testMultipleCarries(solution);

        // 测试6: 大数相加
        System.out.println("\n--- 测试6: 大数相加 ---");
        testLargeNumbers(solution);

        // 测试7: 一个数为0的情况
        System.out.println("\n--- 测试7: 其中一个数为0 \"123\" + \"0\" ---");
        testOneZero(solution);

        // 测试8: 相同长度且有进位
        System.out.println("\n--- 测试8: 相同长度有进位 \"999\" + \"999\" ---");
        testSameLengthWithCarry(solution);

        // 测试9: 长度差异很大
        System.out.println("\n--- 测试9: 长度差异大 \"1\" + \"99999999\" ---");
        testVeryDifferentLengths(solution);

        // 测试10: 连续进位
        System.out.println("\n--- 测试10: 连续进位 \"199\" + \"1\" ---");
        testConsecutiveCarries(solution);

        // 测试11: 复杂进位场景
        System.out.println("\n--- 测试11: 复杂进位 \"9999\" + \"9999\" ---");
        testComplexCarry(solution);

        // 测试12: 边界情况测试
        System.out.println("\n--- 测试12: 最大长度数字 ---");
        testMaxLength(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基础示例：num1 = "11", num2 = "123"
     * 计算过程：
     * 1 1
     * + 1 2 3
     * -------
     * 1 3 4
     */
    private static void testCase1(S27_Easy_415_字符串相加 solution) {
        String num1 = "11";
        String num2 = "123";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");
        printAdditionVisualization(num1, num2);

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"134\")");
        assert result.equals("134") : "期望结果为134";
        System.out.println("✓ 基础示例测试通过");
    }

    /**
     * 测试不同长度：num1 = "456", num2 = "77"
     */
    private static void testCase2(S27_Easy_415_字符串相加 solution) {
        String num1 = "456";
        String num2 = "77";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");
        printAdditionVisualization(num1, num2);

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"533\")");
        assert result.equals("533") : "期望结果为533";
        System.out.println("✓ 不同长度测试通过");
    }

    /**
     * 测试零相加：num1 = "0", num2 = "0"
     */
    private static void testCase3(S27_Easy_415_字符串相加 solution) {
        String num1 = "0";
        String num2 = "0";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"0\")");
        assert result.equals("0") : "期望结果为0";
        System.out.println("✓ 零相加测试通过");
    }

    /**
     * 测试单位数相加：有进位的情况
     */
    private static void testSingleDigits(S27_Easy_415_字符串相加 solution) {
        String num1 = "1";
        String num2 = "9";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"10\")");
        assert result.equals("10") : "期望结果为10";
        System.out.println("✓ 单位数相加测试通过");
    }

    /**
     * 测试多重进位：num1 = "999", num2 = "1"
     * 每一位都需要进位的情况
     */
    private static void testMultipleCarries(S27_Easy_415_字符串相加 solution) {
        String num1 = "999";
        String num2 = "1";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");
        printAdditionVisualization(num1, num2);

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"1000\")");
        assert result.equals("1000") : "期望结果为1000";
        System.out.println("✓ 多重进位测试通过");
    }

    /**
     * 测试大数相加
     */
    private static void testLargeNumbers(S27_Easy_415_字符串相加 solution) {
        String num1 = "123456789";
        String num2 = "987654321";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"1111111110\")");
        assert result.equals("1111111110") : "期望结果为1111111110";
        System.out.println("✓ 大数相加测试通过");
    }

    /**
     * 测试其中一个数为0
     */
    private static void testOneZero(S27_Easy_415_字符串相加 solution) {
        String num1 = "123";
        String num2 = "0";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"123\")");
        assert result.equals("123") : "期望结果为123";
        System.out.println("✓ 其中一个数为0测试通过");
    }

    /**
     * 测试相同长度且有进位
     */
    private static void testSameLengthWithCarry(S27_Easy_415_字符串相加 solution) {
        String num1 = "999";
        String num2 = "999";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");
        printAdditionVisualization(num1, num2);

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"1998\")");
        assert result.equals("1998") : "期望结果为1998";
        System.out.println("✓ 相同长度有进位测试通过");
    }

    /**
     * 测试长度差异很大
     */
    private static void testVeryDifferentLengths(S27_Easy_415_字符串相加 solution) {
        String num1 = "1";
        String num2 = "99999999";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"100000000\")");
        assert result.equals("100000000") : "期望结果为100000000";
        System.out.println("✓ 长度差异大测试通过");
    }

    /**
     * 测试连续进位
     */
    private static void testConsecutiveCarries(S27_Easy_415_字符串相加 solution) {
        String num1 = "199";
        String num2 = "1";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");
        printAdditionVisualization(num1, num2);

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"200\")");
        assert result.equals("200") : "期望结果为200";
        System.out.println("✓ 连续进位测试通过");
    }

    /**
     * 测试复杂进位场景
     */
    private static void testComplexCarry(S27_Easy_415_字符串相加 solution) {
        String num1 = "9999";
        String num2 = "9999";
        System.out.println("输入: num1 = \"" + num1 + "\", num2 = \"" + num2 + "\"");
        printAdditionVisualization(num1, num2);

        String result = solution.addStrings(num1, num2);
        System.out.println("addStrings() -> \"" + result + "\" (期望: \"19998\")");
        assert result.equals("19998") : "期望结果为19998";
        System.out.println("✓ 复杂进位测试通过");
    }

    /**
     * 测试最大长度数字
     */
    private static void testMaxLength(S27_Easy_415_字符串相加 solution) {
        // 构造接近最大长度的数字字符串
        StringBuilder largeNum1 = new StringBuilder();
        StringBuilder largeNum2 = new StringBuilder();

        // 创建长度为100的数字字符串
        for (int i = 0; i < 100; i++) {
            largeNum1.append("9");
            largeNum2.append("1");
        }

        String num1 = largeNum1.toString();
        String num2 = largeNum2.toString();
        System.out.println("输入: 两个长度为100的数字字符串");
        System.out.println("num1 = \"999...999\" (100个9)");
        System.out.println("num2 = \"111...111\" (100个1)");

        String result = solution.addStrings(num1, num2);
        System.out.println("结果长度: " + result.length());
        System.out.println("结果前10位: " + result.substring(0, 10) + "...");

        // 验证结果是否正确（应该是1后面跟着99个1再跟着一个0）
        boolean isCorrect = result.length() == 101 && result.charAt(0) == '1' && result.charAt(100) == '0';
        assert isCorrect : "大数相加结果验证失败";
        System.out.println("✓ 最大长度测试通过");
    }

    /**
     * 辅助方法：可视化加法运算过程
     */
    private static void printAdditionVisualization(String num1, String num2) {
        int maxLen = Math.max(num1.length(), num2.length());

        System.out.println("竖式计算:");
        // 打印第一个数字（右对齐）
        System.out.printf("%" + (maxLen + 2) + "s%n", num1);
        // 打印加号和第二个数字
        System.out.printf("+ %" + maxLen + "s%n", num2);
        // 打印分割线
        for (int i = 0; i < maxLen + 2; i++) {
            System.out.print("-");
        }
        System.out.println();
    }
}
